package com.test.daily.leetcode.y2022.m05.day0523.v02;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/23 上午 07:49
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static class Info {
        int height;
        boolean isBalance;
        public Info(int height, boolean isBalance){
            this.height = height;
            this.isBalance = isBalance;
        }
    }
    public static boolean isBalance2(Node root){
        return process(root).isBalance;
    }
    public static Info process(Node root){
        if(root == null){
            return new Info(0, true);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalance = true;
        if(!leftInfo.isBalance || !rightInfo.isBalance){
            return new Info(height, false);
        }
        if(leftInfo.isBalance && rightInfo.isBalance
        || Math.abs(leftInfo.height - rightInfo.height) > 1){
            return new Info(height, false);
        }
        return new Info(height, isBalance);
    }

    public static boolean isBalance1(Node root) {
        boolean[] ans = new boolean[1];
        process(root, ans);
        return ans[0];
    }

    public static int process(Node root, boolean[] ans) {
        if (!ans[0] && root == null) {
            return -1;
        }
        int leftHeight = process(root.left, ans);
        int rightHeight = process(root.right, ans);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            ans[0] = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}
